package datastructure.queue;

public class LinkedListQueue<E> implements Queue<E> {
    // 使用链表实现队列

    // 定义节点
    private class Node<E> {
        E e;
        Node<E> next;

        // 创建构造函数
        public Node() {
            e = null;
            next = null;
        }

        public Node(E e) {
            this.e = e;
            next = null;
        }

        public Node(E e, Node<E> next) {
            this.e = e;
            this.next = next;
        }
    }

    private int size;
    private Node<E> head, tail;

    public LinkedListQueue() {
        size = 0;
        head = null;
        tail = null;
    }

    // 经过分析知道,当我们添加链表的尾节点时候,这样就可以在链表的尾部进行插入操作,
    // 在链表的首部进行删除操作,这样就形成了一个队列

    @Override
    public void enqueue(E e) {
        // 说明链表中没有节点
        if (tail == null) {
            // 创建一个节点
            Node<E> node = new Node<>(e);
            tail = node;
            // 头和尾部指向头一个节点
            head = tail;
        } else {
            // 说明链表中是有元素的,因此只需要修改尾节点无需关系头结点
            Node<E> node = new Node<>(e);
            tail.next = node;
            // 维护tial将tail指向下一个位置
            tail = tail.next;
        }
        size++;
    }

    @Override
    public E dequeue() {
        // 首先看链表里面还有元素没.
        if (isEmpty()) {
            throw new IllegalArgumentException("操作异常,队列为空");
        }
        // 获取到表头节点
        Node<E> retHead = head;
        // 将表头指向下一个位置,这时候retHead指向的head
        head = head.next;
        // 将retHead指向null,于head断开连接
        retHead.next = null;
        if (head == null) {
            // 维护tail,当表中只有一个数据的时候,删除之后,将tail指向null而不是原来的retHead节点.
            tail = null;
        }
//        tail = head == null ? null : tail;
        size--;
        return retHead.e;
    }

    @Override
    public E peek() {
        return head.e;
    }

    @Override
    public int getSize() {

        return size;
    }

    @Override
    public boolean isEmpty() {

        return size == 0;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("Queue:");
        Node<E> cur = head;
        while (cur != null) {
            sb.append(cur.e + "->");
            cur = cur.next;
        }
        sb.append("null");
        return sb.toString();
    }

    public static void main(String[] args) {
        LinkedListQueue<Integer> queue = new LinkedListQueue<>();

        for (int i = 0; i < 10; i++) {
            queue.enqueue(i);
            System.out.println(queue);
            if (i % 3 == 2) {
                System.out.println(queue.dequeue());
            }
        }

    }

}
